Binary tree preorder traversal [Morris Traversal, Stack]¶
Time: O(N); Space: O(1); medium
Given a binary tree, return the preorder traversal of its nodes’ values.
Example 1:
1
/ \
2 3
Input:root = {TreeNode} [1,2,3]
Output:[1,2,3]
Example 2:
1
\
2
/
3
Input: root = {TreeNode} {1,#,2,3}
Output: [1,2,3]
Note:
Recursive solution is trivial, could you do it iteratively?
[6]:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
1. Morris Traversal Solution¶
[7]:
class Solution1(object):
def preorderTraversal(self, root):
'''
:type root: TreeNode
:rtype: List[int]
'''
result, curr = [], root
while curr:
if curr.left is None:
result.append(curr.val)
curr = curr.right
else:
node = curr.left
while node.right and node.right != curr:
node = node.right
if node.right is None:
result.append(curr.val)
node.right = curr
curr = curr.left
else:
node.right = None
curr = curr.right
return result
[8]:
s = Solution1()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
assert s.preorderTraversal(root) == [1, 2, 3]
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
assert s.preorderTraversal(root) == [1, 2, 3]
2. Stack Solution¶
[9]:
class Solution2(object):
'''
Time: O(N)
Space: O(H)
'''
def preorderTraversal(self, root):
'''
:type root: TreeNode
:rtype: List[int]
'''
result, stack = [], [(root, False)]
while stack:
root, is_visited = stack.pop()
if root is None:
continue
if is_visited:
result.append(root.val)
else:
stack.append((root.right, False))
stack.append((root.left, False))
stack.append((root, True))
return result
[10]:
s = Solution2()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
assert s.preorderTraversal(root) == [1, 2, 3]
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
assert s.preorderTraversal(root) == [1, 2, 3]